%todo: reference "Masked types for sound object initialization" in the journal version.

In this section we discuss related work on ownership and immutability.
We first highlight the relationship between OIGJ and our previous work on ownership (OGJ)
    and immutability (IGJ).
%no space:  The initial idea to unify immutability and ownership appeared in~\cite{li:2008:towards}.
We also survey some of the most relevant related language designs and show how OIGJ
    compares to them.


\subsection{Relationship with OGJ and IGJ}

OIGJ can be thought of as the ``cartesian product'' of OGJ and IGJ:
    OIGJ uses two type parameters to express
    ownership and immutability.
However, the delicate intricacies between ownership and immutability
    required changes to both OGJ and IGJ, making OIGJ more expressive than
    a naive combination. % of both.



\begin{figure}[t]
\newcommand{\YEPP}[0]{+}
\newcommand{\NOPE}[0]{}
\center
\setlength{\tabcolsep}{.3\tabcolsep}
\begin{tabular}{|l|c|c|c|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
    & {OIGJ}
    & {OGJ}
    & {IGJ}
    & {GUT}
    & {UTT}
    & {IOJ}
    & {JOE$_3$}
    \\
    & {}
    & {\cite{PotaninNCB2006}}
    & {\cite{ZibinPAAKE2007}}
    & {\cite{DietlDM2007}}
    & {\cite{MullerR2007}}
    & {\cite{HaackPSS2007}}
    & {\cite{OstlundWC2008}}
    \\
  \hline
  Owner-as-dominator    & \YEPP & \YEPP & \NOPE & \NOPE & \NOPE & \YEPP & \YEPP \\
  Owner-as-modifier     & \NOPE & \NOPE & \NOPE & \YEPP & \YEPP & \NOPE & \NOPE \\
  Readonly references   & \YEPP & \NOPE & \YEPP & \YEPP & \YEPP & \NOPE & \YEPP \\
  Immutable objects     & \YEPP & \NOPE & \YEPP & \NOPE & \NOPE & \YEPP & \YEPP \\
  Uniqueness            & \NOPE & \NOPE & \NOPE & \NOPE & \NOPE & \NOPE & \YEPP \\
  Ownership transfer    & \NOPE & \NOPE & \NOPE & \NOPE & \YEPP & \NOPE & \NOPE \\
\hline
Factory method pattern  & \YEPP & \YEPP & \YEPP & \YEPP & \YEPP & \NOPE & \YEPP \\
  Visitor pattern       & \YEPP & \NOPE & \YEPP & \NOPE & \NOPE & \NOPE & \NOPE \\
Sun's \code{LinkedList} & \YEPP & \NOPE & \NOPE & \NOPE & \NOPE & \NOPE & \NOPE \\
%Case studies available  & \YEPP & \NOPE & \YEPP & \NOPE & \NOPE & \NOPE & \NOPE \\
  \hline
\end{tabular}
\caption{Features supported by various language designs.}
\label{Figure:Comparison}
\end{figure}


\textbf{Ownership Generic Java (OGJ)}~\cite{PotaninNCB2006} demonstrated how
    ownership and generic types can be unified as a language feature.
OGJ featured a single owner parameter for every class that was treated in the same
    way as normal generic type parameters, simplifying the language, the formalism,
    and the implementation.

OGJ completely prohibits wildcards as owner parameters, e.g., \code{Point<?>},
    whereas OIGJ relaxes this rule and allows wildcards on stack variables,
    which enables writing the \code{equals} method
    (see \textbf{Generic Wildcards rule} in \Ref{Section}{typing-rules}).

In OGJ, a method may have generic parameters that are owner parameters,
        e.g.,
        \begin{algorithmic}
        \STATE \code{class Foo<O extends World> \lb}
        \STATE \code{~<\underline{O2 extends World}> void bar(Object<\underline{O2}> o) \lb \ldots \rb}
        \end{algorithmic}
However, OGJ required that
    the parametric owners are \emph{outside}
    the owner of the class, e.g., $\code{O} \Oprec \code{O2}$.
This rule is very restrictive, however it guarantees that the ownership
    structure is a tree.
OIGJ removed this rule at the cost of complicating the
    ownership structure: it is a \emph{directed acyclic graph} (DAG) instead of a tree.

Finally, OIGJ can express temporary
    ownership within a method by using a fresh owner parameter
    (see \textbf{Fresh owners} in \Ref{Section}{typing-rules}).

\textbf{Immutability Generic Java (IGJ)}~\cite{ZibinPAAKE2007} showed
    how generic types can be used to provide support for readonly references
    and object immutability. % in a simple manner similar in spirit to OGJ.
OIGJ used ownership information to improve the expressiveness of IGJ.
Specifically, certain restrictions in IGJ no longer apply in OIGJ for \this-owned objects.
For example, \Raw is \emph{not} transitive in IGJ,
    e.g., the assignment to \code{next} in \Ref{Figure}{OIGJ-LinkedList}
    on lines~\ref{OIGJ:assignment:ctor1} and~\ref{OIGJ:assignment:addAll}
    is illegal in IGJ, thus limiting creation of immutable objects.
In contrast, \Raw is transitive in OIGJ for \this-owned fields (see
\textbf{Field assignment rule} in \Ref{Section}{typing-rules}),
    and therefore there was no need to refactor the collections' code.

IGJ includes an \code{@Assignable} annotation on fields that permits field assignment %to those fields
    even in immutable objects.
The \code{@Assignable} annotation indicates that a given field
% (for example, a cache)
is not part of the object's abstract state.
This is necessary to type-check caches, lazily-initialized fields, and
other programming idioms.
%For example, the immutable class \code{String} contains
%    a lazily-initialized field for caching the hash-code,
%    i.e., field \code{hash} is assigned inside the \code{hashCode}
%    method and not in the constructor.
OIGJ removed this annotation to simplify the formalism.  This also guarantees
representation immutability as well as immutability of the abstraction:
the fields of a cooked immutable object never change.
Our implementation supports the \code{@Assignable} annotation.

IGJ only permits a single immutability parameter, which simplifies the subtyping rule.
In contrast, types in OIGJ can have multiple immutability parameters, for example,
    \code{Iterator<O,\underline{ItrI,CollectionI},E>}.
%The cost is a slightly more complicated \textbf{Same-class subtype relation} in OIGJ.
Because IGJ uses a single immutability parameter,
    the immutability of an iterator and its underlying collection must be the same.
Thus, in IGJ, %, using,
    method \code{next()} must be readonly (or you couldn't iterate over a readonly list),
    and therefore
    we had to use an \code{@Assignable} annotation on \code{ListItr.current}
    (line~\ref{OIGJ:assignable} in \Ref{Figure}{OIGJ-LinkedList}).
In contrast, in OIGJ, we guard \code{next()} with a mutable \code{ItrI} (line~\ref{I:next}),
    and guard \code{remove()} with a mutable \code{CollectionI} (line~\ref{I:remove}).
%Furthermore, building OIGJ on top of cJ removed the following three typing rules from IGJ:
%(1) \this rule,
%(2) Method overriding rule, and
%(3) Method invocation rule.


\subsection{Relationship with other work}

% todo{In camera-ready copy, note that that is just a diffrenent syntax
% for what was already implemented in ConstJava and Javari.}
OIGJ uses method guards borrowed from \emph{cJ}~\cite{HuangZS2007:cJ}.
(The OIGJ implementation uses annotations syntax instead.) % of the method guards syntax.)

In what follows, we have room to survey only closely related papers.
% from the rich literature on immutability and ownership.
\Ref{Figure}{Comparison} compares OIGJ to some of the previous work described below.


\textbf{Mutability and encapsulation} were first combined by
Flexible Alias Protection (FLAP)~\cite{NobleVP98}.
FLAP inspired a number of proposals including ownership
types~\cite{ClarkePN98}
and confined types~\cite{VikekB99}.
Capabilities for Sharing~\cite{BoylandNR2001}
describes the fundamentals underlying various encapsulation and
mutability approaches by separating ``mechanism'' (the semantics of
sharing and exclusion) from ``policy'' (the guarantees provided by the
resulting system). Capabilities gives a lower-level semantics that can
be enforced at compile or run time.  A reference can possess any
combination of these 7 access rights: read, write, identity
(permitting address comparisons), exclusive read, exclusive write,
exclusive identity, and ownership (giving the capability to assert
rights).  Immutability, for example, is represented by the lack of the
write right and possession of the exclusive write right.
Finally, \emph{Fractional Permissions}~\cite{BoylandRZ2009}
    can give semantics to various annotations such as unique, readonly, method effects,
    and
    an ownership variant called \emph{owner-as-effector} in which
    one cannot read or write owned state without declaring the appropriate
    effect for the owner.
%The owner-as-dominator policy is structural, whereas
%    owner-as-effector is semantic, thus allowing inlining method calls.


\textbf{Ownership types}~\cite{ClarkeD2002,BoyapatiLR2002,BoyapatiLS2003}
    impose a structure on the references between objects in a program's memory.
OIGJ and other work~\cite{PotaninNCB2006,OstlundWC2008} enforce
    the owner-as-\emph{dominator} disciplines.
Generic Universe Types
    (\textbf{GUT})~\cite{MuellerPoetzsch-Heffter99a,DietlDM2007} enforce owner-as-\emph{modifier}
    by using three type annotations: \code{rep}, \code{peer}, and \code{readonly}.
\code{rep} denotes representation objects (similar to \This),
    while \code{peer} denotes objects owned by the same owner (similar to \hO).
\textbf{UTT}~\cite{MullerR2007} is an extension of Universe Types
    that supports ownership transfer by utilizing a modular static analysis, which is useful for merging data-structures
    or complex object initialization.
%todo{I am inclined to say that it is possible to support both
%  owner-and-dominator and owner-as-modifier, and cite our technical report.}

MOJO~\cite{CameronDNS2007} can express multiple ownership: objects can have more than one owner at run time.
OIGJ supports only a single \emph{owner} at run time.
(OIGJ supports multiple \emph{owner parameters}, but according to the \textbf{Ownership nesting rule},
    all owner parameters are inside the first owner parameter.)
%todo{This seems wrong on two levels.  First,
%  OIGJ permits multiple owner parameters; it should be clarified that this
%  is not what we are talking about.  Second, Section~5.1 says:  ``OIGJ removed this rule at the cost of complicating the
%    ownership structure: it is a \emph{directed acyclic graph} (DAG)
%    instead of a tree.'', so the implied contrast with MOJO is incorrect
%    and needs to be clarified.}
%In contrast, objects in OIGJ have a single owner.

Jo$\exists$~\cite{CameronD2009} supports variant subtyping over the owner parameter
    by using existential types.
OIGJ supports wildcards used as owners for stack variables, but those are less flexible than Jo$\exists$.
For example, Jo$\exists$ can distinguish a list of students that may
    have different owners, from a list of student that share the same unknown owner.

\textbf{Immutability and ownership.}
Similarly to OIGJ,
    Immutable Objects for a Java-like Language (\textbf{IOJ})~\cite{HaackPSS2007}
    associates with each type its mutability and owner.
In contrast to OIGJ, IOJ does not have generics,
    nor readonly \emph{references}. %(only immutable \emph{objects}).
Moreover, in IOJ, the constructor cannot leak a reference to \this.
% "Type-based Object Immutability with Flexible Initialization"
Haack and Poll~\cite{HaackPSS2007} later added flexible initialization of immutable objects,
    i.e., an immutable object may still be mutated after its constructor returns.
They use the annotations \code{RdWr}, \code{Rd}, \code{Any}, and \code{myaccess},
    which corresponds to our \code{Mutable}, \code{Immut}, \code{ReadOnly}, and \code{I}.
In addition, they have an inference algorithm that automatically infers the end of object initialization phases.
(Their algorithm infers which variables are \code{Fresh(n)}, which resembles our \code{Raw}.
    However, the programmer cannot write the \code{Fresh} annotation explicitly.)
% "TIFI+: A Type Checker for Object Immutability with Flexible Initialization" has exactly the same type-system.
% Because "Fresh" cannot be written on method parameters, it is not clear how they implement LinkedList



{X10}~\cite{NystromSPG2008} supports constrained types that can refer to properties and final local variables.
%    and can be adapted for ownership purposes, e.g.,  \code{Entry\lb{}owner==\underline{list}\rb~e = \underline{list}.header;}\\
X10 supports cyclic immutable structures by using \code{proto} annotations,
    which are similar to our immutability~\hI and the notion of cookers.
However, both X10 and IGJ cannot type-check Sun's \code{LinkedList} because an object becomes cooked when its constructor finishes.
It is possible to refactor \code{LinkedList} to fit X10's typing-rules
    by using a recursive implementation, but then you risk a stack-overflow when creating large lists.
Delayed types~\cite{FahndrichX2007}, which are similar to X10's \code{proto},
    are used to verify non-null fields or other heap-monotonic properties.

\textbf{JOE$_3$}~\cite{OstlundWC2008} combines ownership (as dominators, not modifiers),
    uniqueness, and immutability.
It also supports owner-polymorphic methods, but not existential owners.

Frozen Objects~\cite{LeinoMW2008} show how ownership can help support immutability
by allowing programmers to decide when the object should become immutable. This system
takes a verification approach rather than a simple type checker such as OIGJ. Frozen Objects show
how flexible the initialization stage can potentially be in the presence of ownership and immutability,
while OIGJ shows how much flexibility can be achieved while staying at the type checking level.

\textbf{Readonly references} are  found in \CC (using the \const{} keyword),
JAC~\cite{KnieselT2001}, modes \cite{SkoglundW2001},
Javari \cite{TschantzE2005}, etc.
Previous work on readonly references
    lack ownership information.
Boyland~\cite{Boyland2005} observes that readonly does not address
observational exposure, i.e., modifications on one side of an
abstraction boundary that are observable on the other side.
Immutable objects address such exposure because their state cannot
change.
% , e.g., an immutable address in a person object can be safely
% shared among many person objects.


\textbf{List iterators} pose a challenge to ownership because
    they require a direct pointer to the list's privately owned entries,
    thus breaking the owner-as-dominator property.
Both OIGJ and SafeJava~\cite{BoyapatiLS2003} allow an inner instance
    to access the outer instance's privately owned objects.
Clarke~\cite{ClarkeD2002} suggested to use iterators only with stack variables,
    i.e., you cannot store an iterator in a field.
It is also possible to redesign the code and implement iterators without violating ownership,
    e.g., by using internal iterators or magic-cookies~\cite{Noble2000}.

% LocalWords:  OGJ IGJ cartesian IOJ UTT Readonly wildcards readonly ItrI cJ
% LocalWords:  CollectionI ListItr MOJO proto JAC Boyland SafeJava
